package com.Twenty_Six;

import java.util.ArrayList;
import java.util.List;

/**
 * 491. 递增子序列
 * 给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
 *
 * 数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/increasing-subsequences
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 2022/09/26 17:40
 */

public class Solution491 {

    List<List<Integer>> list=new ArrayList<>();
    List<Integer> path=new ArrayList<>();

    public List<List<Integer>> findSubsequences(int[] nums) {
        backtracking(nums,0);
        //System.out.println(list.size());
        return list;
    }

    public void backtracking(int[] nums,int startIndex){
        if (path.size()>1)
        {
            list.add(new ArrayList<>(path));
        }
        int[] used =new int[201];
        for (int i=startIndex;i<nums.length;i++)
        {
            if ((!path.isEmpty()&&nums[i]<path.get(path.size()-1))|| used[nums[i]+100]==1) continue;
            used[nums[i]+100]=1;
            path.add(nums[i]);
            backtracking(nums,i+1);
            path.remove(path.size()-1);
            //used[nums[i]+100]=0;
        }
    }

    public static void main(String[] args) {
        Solution491 solution491=new Solution491();
        int[] nums={1,2,3,4,5,6,7,8,9,10,1,1,1,1,1};
        System.out.println(solution491.findSubsequences(nums));
    }

}
